.nr PO 0.5i
.nr LL 7.0i
.ls 1
.LP
.bp
.nf
test(X) :-
    pipe([10,5,3,1,
        7,2,4,6,5,
        100,5,12,150], X).

pipe(X,Y) :-
        lap(X,XX),
        mergeAll(XX,Y).

mergeAll([Single],Single) :- !.
mergeAll(S,Out) :-
        merge2(S,Out1),
        mergeAll(Out1,Out).

merge2([],[]).
merge2([Single],[Single]).
merge2([A,B|T],[YY|Y]) :-
        merge(A,B,YY),
        merge2(T,Y).

merge(L,[],L).
merge([],L,L).
merge([A|X],[B|Y],[A|Z]) :-
        A =< B, !,
        merge(X,[B|Y],Z).
merge([A|X],[B|Y],[B|Z]) :-
        merge([A|X],Y,Z).

lap([],[]).
lap([X|L],[[X]|S]):-
        lap(L,S).


Fig.9  merge sorrt in Prolog
.bp
test :- Strdata = [10,20,5,100,1,6,2,3],
        datagen(Strdata,Data), pipe(Data,Out),
        length(18), #write(Out).

        % Data Generator

datagen([],[]).
datagen([H|T],Out) :-
        Out = [H],
        @T = T, @datagen(T,Out).

        % Pipeline Merge Sorter

pipe(I0,Out) :-
        I1 = [], I2 = [], Out = [],
        X1 = [], Y1 = [], Z1 = [], T1 = 1,
        X2 = [], Y2 = [], Z2 = [], T2 = 1,
        X3 = [], Y3 = [], Z3 = [], T3 = 1,
        #proc(I0,I1 ,X1,Y1,Z1,T1,2,1),
        #proc(I1,I2 ,X2,Y2,Z2,T2,4,2),
        #proc(I2,Out,X3,Y3,Z3,T3,8,4).

    % Processor Unit

proc(I,O,X,Y,Z,T,P,PP) :-
    if (X=[],Y=[],I=[]) then (
            @X=X, @Y=Y, @Z=Z, @O=[], @T=1
    ) else ((
            if T=<PP then
                append(Z,I,Zn), @Z=Zn, Xn=X, Yn=Y,
                @T=T+1
            else
                append(Y,I,Yn), @Z=[], Xn=X,
                if T<P
                   then @T=T+1 else @T=1
        ), (
            if (Xn=[],Yn=[]) then (
                @O=[], @Y=Yn,
                if T=PP
                    then @X=Zn else @X=Xn
            ) else if (Xn=[A|L],Yn=[]) then (
                @O=[A], @Y=Yn,
                if T=PP
                     then @X=Zn else @X=L
            ) else if (Xn=[],Yn=[B|N]) then (
                @O=[B], @Y=N,
                if T=PP
                      then @X=Zn else @X=Xn
            ) else if (Xn=[A|L],Yn=[B|N]) then
                if A<B then
                    @O=[A], @X=L, @Y=Yn
                else
                    @O=[B], @Y=N, @X=Xn
        )).

append(Nil,L,L1) :- Nil=[],L=L1.
append(X,L,Y) :-[H|T]=X,[H1|M]=Y,
     H=H1,append(T,L,M).

Fig.10  pipeline merge sort in Tokio



.bp

| ?- tokio test.
[][][][][][][][][][][1][2][3][5][6][10][20][100][]
18 clock and 18.0834 sec.

yes


Fig.11 sample execution

.bp
% cprolog
cprolog
C-Prolog version 1.5
tokio consulted 57168 bytes 66.6166 sec.
| ?- com([tm,user],user).            % start compile
|: p :- q, r.                        % input clause
p(_0,_1):-q(_0,_2),r(_2,_1).         % compile output
|: p :- next(q), r.
p([$t((q(_0,_1),_2),_3,_4,_5)|_0],_6):-
   r([$t(_2,_3,_4,_5)|_1],_6).
|: p :- next(next(next(r))).
p(
    [_0,_1,$t((r(_2,_3),_4),_5,_6,_7)|_2],
    [_0,_1,$t(_4,_5,_6,_7)|_3]).
|: p(X,Y) :- X=Y.
p(_0,_1,_2,_2):-
    unifyNow(_0,_3),unifyNow(_1,_3).
|: eq(X,X).
eq(_0,_1,_2,_2):-unifyAll(_0,_1).
|: p(X,Y) :- @X=Y.
p(_0,_1,_2,_2):-
    unifyNext(_0,_3),unifyNow(_3,_4),
    unifyNow(_1,_4).


Fig.13 Sample compile


.bp

yes
| ?- tokio length(5),X=1,
counter(X),#write(X).
123456
X = $t(1,$t(2,$t(3,
    $t(4,$t(5,$t(6,_))))))


Fig.14  Temporal variable representation




|: p(f(X),Y) :- X=Y.
$f1(f(_1),_1):-!.
$f1($t(f(_1),_2),
   $t(_1_3)):-$f1(_2,_3).
p(_103,_104,_55,_55):-
   $f1(_103,_113),
   unifyNow(_113,_83),
   unifyNow(_104,_83).

Fig.15  Generating of unifier




                |clause size  |    execution time (sec)
                |(byte size)  |           on Vax730
_____________________________________________________________
program         |source object| Interpreter  compiler   prolog
_____________________________________________________________
append  (30list)|    3      3 |     10.6        0.8      0.13
    (all state) | (49)  (177) |
append          |    3      3 |     27.9        2.0      0.13
  (single state)| (92)  (224) |
pipeline merge  |    7     33 |    154.4       18.1      ----
    sorter      |(1799)(8796) |


Fig.16  Tokio compiler
